package 简单.其他;

/**
 * 给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一
 * 个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。
 * <p>
 * 来源：https://leetcode-cn.com/problems/find-smallest-letter-greater-than-target/
 */
public class 寻找比目标字母大的最小字母_744 {

    public static void main(String[] args) {

        char[] chars = "cfj".toCharArray();
        char c = efficientNextGreatestLetter(chars, "d".toCharArray()[0]);
        System.out.println(c);

    }

    //二分法，时间复杂度O(logN)
    public static char efficientNextGreatestLetter(char[] letters, char target) {
        //1,定义左右边界
        int left = 0, right = letters.length - 1;
        int mid;
        //如果没有大于target的字符，则返回第一个。
        char min = letters[0];
        while (right >= left) {
            //取中间值
            mid = left + (right - left) / 2;
            //符合条件的的值
            if (letters[mid] > target) {
                min = letters[mid];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return min;
    }

    //遍历，因为已经排序好了，只要找到大于target的值就返回，时间复杂度O(N)
    public static char nextGreatestLetter(char[] letters, char target) {
        for (char letter : letters) {
            if (letter > target) {
                return letter;
            }
        }
        return letters[0];
    }

}
